The discrete Walsh-Hadamard transform (WHT) is a known signal processing tool with applications in areas as disparate as image compression, multi-user transmission cellular networks (CDMA), coding, and spectroscopy. The discrete Walsh-Hadamard transform has a recursive structure which, similar to the fast Fourier transform (FFT) algorithm for computing the discrete Fourier transform (DFT) of the signal, allows a fast computation with complexity O(N log N) in the dimension of the signal N.
A number of publications have addressed the particular problem of computing the DFT of an N dimensional signal with time complexity sub-linear in N, assuming that the signal is K-sparse in the frequency domain. Being sublinear in N, all the methods proposed in said publications improve over the time complexity O(N log N) of the FFT. Such algorithms are generally called sparse FFT (sFFT) algorithms. In particular, a very low complexity algorithm for computing the 2D-DFT of a √{square root over (N)}×√{square root over (N)} signal has become available.
In a similar line of work, based on the sub-sampling property of the DFT in the time domain, resulting in the aliasing in the frequency domain, a novel low complexity iterative algorithm was developed in the art by borrowing ideas from the coding theory to recover the non-zero frequency components.
Upon reviewing the knowledge available in the art summarized above it has become apparent for the inventors of the present invention that further needs exist in the art insofar developing further some of the useful properties of the discrete Walsh-Hadamard transform, especially the subsampling property. It was further evident that a need exists to show that the subsampling in the time domain allows to induce a controlled aliasing pattern over the transform domain in components, namely, instead of obtaining the individual components in the transform domain, it is possible to obtain the linear combination of a controlled collection of components (aliasing), which creates interference between the non-zero components if more than two of them are involved in the induced linear combination.